package bin_tree.oj;

import java.util.LinkedList;
import java.util.Queue;

public class Num662 {
    public static class RrturnType{
        TreeNode node;
        int depth; //深度
        int pos;  //位置

        RrturnType(TreeNode n, int d, int p){
            node = n;
            depth = d;
            pos = p;
        }
    }

    public int widthOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<RrturnType> queue = new LinkedList<>();
        queue.add(new RrturnType(root, 0, 0));
        int curDepth = 0;
        int left = 0;
        int res = 0;
        while(!queue.isEmpty()){
            RrturnType cur = queue.poll();
            if(cur.node != null){
                queue.add(new RrturnType(cur.node.left, cur.depth + 1, cur.pos * 2));
                queue.add(new RrturnType(cur.node.right, cur.depth + 1, cur.pos * 2 + 1));
                if(curDepth != cur.depth){
                    curDepth = cur.depth;
                    left = cur.pos;
                }
                res = Math.max(res,cur.pos - left + 1);
            }
        }
        return res;
    }
}
